This copyrighted material is free of charge for individual use. PDF files for easy printing and reading over the internet are here, as well as source code for the program listings. However, people who want to use this textbook to teach a class are to fill out the 5-minute questionaire at the end of this webpage and email it to me, and in response I will always give permission to use the textbook free of charge in the class. This survey data will help me get this book published in the normal way. It is already in publishable form, even copy-edited, except the artwork should be redrawn by professionals.

Preface for Instructors

The main objective of this CS1 book is to introduce object-oriented software design at the very beginning, so it can be developed slowly and thoroughly. We do this in the context of a large number of realistic software packages. From the first week, students begin to develop a feel for what it is like to be a practicing computer scientist.

In general, a primary goal for the first third of the semester of a CS1 course should be that students learn to write realistic and useful object-oriented programs with at least the following two levels of coding, using only the Sun standard library:

1. The main logic that is primarily a matter of sending messages (method calls) to one or more objects to (a) carry out sequences of actions or (b) ask true-false questions to determine which actions to carry out (selection and repetition).
2. One or more classes of objects that define the various messages (instance methods) in terms of operations with numeric instance variables and Sun library objects, particularly String objects.

Most textbooks work bottom-up to this milestone, beginning with numeric types and operations. Control structures and expressions are introduced and illustrated in this numeric context. Examples in the first half of such a textbook are usually small, self-contained, unrealistic main methods. This textbook by contrast works top-down to this milestone -- objects first, beginning in the first ten pages.

We start with object design: The analysis of a problem leads to deciding what objects we will need, what actions they can take and what queries they can answer, so we can accomplish the given task. In other words, object design is choosing the public methods that the objects need to have and deciding how they will be used. Once we have settled those questions, we can think about how to implement the objects, i.e., what their private instance variables are and how we code the methods. Chapter One is a preliminary overview chapter. Chapters Two and Three concentrate on object design using primarily instance methods; the conditions for ifs and whiles are entirely in terms of method calls by objects, not numeric expressions. Chapter Four introduces instance variables for the implementation of objects, thereby allowing stand-alone programs with no book-supplied classes that hide implementation details. Chapter Five introduces class variables.

The links in the rest of this webpage are to PDF files. Table of contents and appendices are at this link. Note that all material needed for the AP CS A exam is in Chapters 1-7 plus Sections 10.1-10.4, 11.1-11.3, and 13.1-13.4. All of the AB exam material is in the book as well, mainly in Chapters 12 through 18.

Reaching the first milestone: stand-alone object-oriented programs early

Chapter One outlines basic algorithm design techniques that are illustrated multiple times in every chapter thereafter. It presents a Logo-like context in which students can write, compile and execute small but interesting graphics application programs in the first week of class. Experience has shown that students enjoy applying these method calls without feeling a strong need to first see the underlying implementation of the Java commands that move the Turtle, just as Java programmers use Graphics methods without feeling a strong need to see Sun's underlying coding for them. The complete implementation of the Turtle class is given later in this book; for now, students create and use Turtles without dealing directly with JApplet or JFrame at all.

Chapter Two describes basic method calls for one particular context we call Vic objects. A Vic object is a fixed-length sequence of elements that can be shifted around. It represents a component of a small electronic appliance. Students learn to develop various small application programs using Vic objects and, for more complex logics, to develop subclasses of Vic containing instance methods called by a main method. The if and if-else statements are introduced for use in such methods, so that the actions taken are method calls that modify the state of an object and the conditional tests are method calls that query the state of an object. This contrasts with the usual numeric context, where the examples of if-statements test conditions of numeric inequality and perform actions that read/compute/write numbers. In the Vic context, the input is the initial state of the objects and the output is the final state of the objects.

Chapter Three continues with the Vic context. Parameters and while-statements are introduced for situations where an object repeats an action until a certain condition becomes true. This makes the programming problems complex enough to justify a thorough discussion of the five-step object-oriented paradigm for the analysis, design, and implementation of software that was introduced in Chapter One and illustrated several times since then. Note that it is not appropriate to introduce the student to all three looping statements in Chapter Three; for-statements are generally for situations where a counter is incremented, and such situations do not even arise until Chapter Four. An advantage of this is that students find loops easier to understand when the full range of possibilities is postponed for a bit.

Chapter Four introduces instance variables and input/output in a game-program context, which finishes the top-down presentation of the development of stand-alone programs. Thus students reach this first milestone, the development of realistic object-oriented programs using only the Java Sun library, by the end of the fourth week of a regular semester. And they make the journey while immersed in totally object-oriented contexts.

Students find the concept of inheritance quite natural when they only have instance methods without instance variables. This avoids the alternatives of either a long complex main method or several shorter class methods, neither of which feels natural in Java. After three chapters of using simple inheritance, students are ready for inheritance with polymorphism in Chapter Four, which is necessary for an honest presentation of applets (otherwise how do you explain why writing a method heading as public void paint(Graphics2D page) causes a blank drawing area?). Additional extended examples using inheritance are implemented in Chapters Five, Seven, Eleven, Fourteen, and Fifteen.

The rest of the book

Chapter Five completes the basic object-oriented language features with a discussion of class methods, class variables, and final variables. It includes an implementation of a Vic simulation using Strings, and finishes with an extended case study on networks. Chapter Five also introduces recursion (though it can be postponed for a while, since recursion is not used again until Chapters Thirteen, Fourteen, and Fifteen).

Chapter Six cover basic language features used throughout the rest of the book: double, long, and char types; more String methods; and additional Sun library input/output methods (there is no book-specific i/o class to shield the students from Java's complexities).

Chapter Seven thoroughly discusses one-dimensional arrays in the context of a personnel database. It includes sequential search, the insertion sort, and an introduction to two-dimensional arrays. Every chapter thereafter illustrates the use of arrays in a different context to solve different problems. However, some instructors prefer to delay arrays until later in the course. To facilitate this, the first part of each of Chapters Eight through Eleven does not use arrays; simply postpone 8.7-8.10, 9.9-9.11, 10.6-10.8, and 11.7-11.8. Arrays are used heavily beginning in Chapter Twelve. Multidimensional arrays are restricted to a single section in Chapter Seven plus a substantial part of Chapter Twelve.

The first seven chapters cover the basic Java language, for which the software packages they discuss are a thin veneer. The last eight chapters emphasize analysis and design more heavily. Each discusses the process for developing a different software package, illustrating a reasonable approach to the construction of small to medium software suites as well as the new language concepts of that chapter. Most of these later chapters begin with a one or two-page analysis of the new software situation and a partial object design to motivate the material in the chapter. Although these software situations were shaped to the language needs at that point, a primary purpose is to deepen the students' understanding of software analysis, design, and implementation. There is enough material that even a two-quarter sequence can omit the major part of several of these applications.

Chapter Eight describes graphics methods and applets. It is not needed for the rest of the book. The essential material of Sections 8.1-8.3 are accessible directly after Section 4.7. However, if your primary purpose is simply to let students enjoy graphical programming early, the Logo-like Turtle application programs in Chapter One should suffice (Turtles provide their own JFrame so students do not deal with those complexities so early).

Chapter Nine introduces event-handling and frames. This is accessible directly after Section 4.7 and independent of the material on applets. The only new Java language feature is inner classes, which are not used elsewhere in the book. Listing 9.5 in particular provides a simple template for GUIs. The MVC pattern used for the case study of Chapter Six is used again for this chapter's case study.

Chapter Ten discusses the throwing and catching of Exceptions. The first three sections of this chapter contain all the new language features for the rest of the book. They include elementary text file input, since that is the most common use of checked Exceptions. These first three sections are accessible directly after Section 6.4.

Chapter Eleven describes and illustrates the use of interfaces and abstract classes. The case study develops subclasses of an abstract Numeric class: one to represent fractions, one to represent complex numbers, and one to represent integers up to 54 digits long. The first four sections of this chapter contain all the new language features for the rest of the book, including a discussion of the Double and Integer classes.

Chapter Twelve goes deeply into file input and output and gives substantial practice with multidimensional arrays. Both topics are used in the case study.

Chapter Thirteen presents the selection sort, the insertion sort, and three N*log(N) sorting methods, all in the context of an array of Comparable objects. It ends with a section on Data Flow Diagrams, which can be covered much earlier in the course if desired.

Chapter Fourteen is a gentle introduction to the use of linked lists and recursion to implement stacks and queues. An array implementation is given first so that students can compare the two kinds of implementation. Then priority queues are implemented in two different ways with arrays and again with linked lists.

Chapter Fifteen presents the full Collection and Iterator interfaces and implements them both with arrays and linked lists.

Additional features

• This book has over 350 exercises with the answers plus over 350 exercises without answers. Both groups are a mix of easy, medium, and hard. These exercises are placed at the ends of the appropriate sections. Over half of the exercises are of the form "Write a method to do so-and-so", since that is the kind of exercise CS1 students need most. Additional exercises ask for modifying existing code, drawing UML diagrams, and generally reinforce concepts learned. All code in examples and in exercise answers has been successfully compiled using both Java 1.2 and Java 1.3.
• Appendices include a summary of the programming style principles scattered through the book, a glossary, an alphabetical list of common compile-time errors with a translation into student terms of what they really mean, an overview-tree of the 150-some Sun library classes described in the book (showing superclasses and packages), and over 100 major programming project assignments organized by chapter.
• Several concepts that computer science majors can expect to see in advanced courses are discussed on an introductory level. For instance, a deceptively simple trio of classes for nodes in a network is developed in a case study in Chapter Five; recursion leads to a solution of the Traveling Salesman Problem. Other optional material introduces the theory of computation, the merge sort, postfix expressions, and binary search trees.
• Each section that introduces new Java language elements ends with a box giving a formal summary of the syntax and semantics. Each chapter starts with an overview and ends with a thorough review that includes all new language features, all new Sun library methods, and all definitions of essential vocabulary items introduced in the chapter. Also, Chapter Five ends with a complete review of all Java language features and Sun library methods up to that point.
• In Chapters Five through Fifteen, the last section or two of each chapter gives a brief description and illustration of additional Sun library methods and classes not used elsewhere in the book. These are sufficiently similar to methods and classes covered thoroughly in the normal text that they do not need an extended discussion. Isolating the less crucial Sun library classes this way makes them available for use in major projects or as a reference in later courses while reducing the burden on students' memories. These sections are starred to indicate they are not included in chapter reviews.
• A clear and well-structured method for analysis and design of software is introduced in Chapter One and used several times in every chapter. It emphasizes designing in English before writing in Java.
• All material needed for the AP CS A exam is in Chapters 1-7 plus Sections 10.1-10.4, 11.1-11.3, and 13.1-13.4. Almost all of the AB exam material is in the book as well.
• UML is introduced in Chapter Two and used several times in every later chapter except Thirteen (which discusses sorting algorithms rather than object classes). It is consistent with the representation of relationships among classes used by BlueJ (which is described at the end of Chapter Four).
• Javadoc-conformant documentation is introduced in Chapter Two and used consistently thereafter.

Sequencing

The following chart applies only to the first half or so of Chapters 8-11, because Chapter Seven is needed for the last part of each of those chapters. Chapters Fourteen and Fifteen are technically independent of each other, but the former has a much gentler introduction to linked lists than the latter.

This text has been classroom-tested both in a first course in programming and in a course for students who have previously had a different programming language. To accommodate the latter, the material in each chapter has been organized so that all of the new language features are covered in the first part (generally half to two-thirds of the chapter), with the bulk of the examples of software design in the latter part of the chapter.

This means that beginning students see definitions early in the chapter with shorter examples and then see extended examples reinforcing the concepts and language features again later in the chapter. And it means that a course for students who have substantial previous programming experience can cover all of the language material much more rapidly, specifically, Sections 2.1-2.8, 3.1-3.6, 4.1-4.7, 5.1-5.4, 6.1-6.5, and 7.1-7.6. The rest of each of those chapters can be skipped or left for these experienced students to read on their own.

This textbook can be used in ways other than the primary text. For example, if you love Karel the Robot but want a book that will carry forward with object-oriented development, then teach Karel for a number of weeks and then start this text at Chapter Four or Five or Six (depending on how far you get in the Karel material). Or if your textbook delays object-oriented material too long, you may wish to supplement it with Chapters Two through Five. Or if your textbook does not give as much drill on array algorithms as you think best, add Chapter Seven, emphasizing Sections 7.6 and 7.7.

Permission to use this textbook

If you want to use this textbook in a class, either as the main text or as a supplement, fill in the answers to the following six questions and paste them into an email to jonesw@ccsu.edu. You will receive permission by return mail. There is no charge for using the book in a class; I just want to know who is using it. I will also send an instructor's manual to you (after April, when I finish reworking it).

1. Your name: ____

2. Name of school: ____

3. Semester/quarter/period you expect to use it: from date ________ to date ________

4. Estimated number of students: ____

5. Which chapters do you expect your students to use: ___

6. Check one of the following: Will you use it as

(a) the primary and required text. ___

(b) a required supplement. ___

(c) a suggested supplement. ___

Java Au Naturel

by William C. Jones, Jr. copyright 2002

The first link in the following is the pdf file for the text material. The second link ("listings") is the source code for the program listings, in a form from which you can copy-and-paste.

Table of Contents and Preface to Student 8 pages

Running the programs in Chapter One requires this file: Turtle.java

Running the programs in Chapters Two and Three requires this file: Vic.java

Chapter 1 Objects 34 pages listings

overview. instance methods for Turtles (used for drawing pictures).

Chapter 2 Conditionals and Boolean Methods 35 pages listings

instance methods. if and if-else statements. boolean operators. UML.

Chapter 3 Loops and Parameters 33 pages listings

while statements. more on UML. parameters.

Interlude Integers and For-loops 6 pages included with Chapter Four

Chapter 4 Instance Variables 38 pages listings

JOptionPane for I/O. constructors. inheritance. polymorphism. BlueJ.

Chapter 5 Class Methods and Class Variables 34 pages listings

scope. final variables. networks and recursion (optional).

Review: Overall Java Language So Far 6 pages included with Chapter Five

Chapter 6 Basic Data Types and Expressions 42 pages listings

doubles, Strings, chars, longs. Math. MVC pattern.

Chapter 7 Arrays 40 pages listings

array algorithms. sequential search. insertion sort. basic 2-dim arrays.

Chapter 8 Elementary Graphics 34 pages listings

applets and graphics.

Chapter 9 Event-Driven Programming 43 pages listings

frames and components. textfields and buttons. more MVC. sliders, etc.

Chapter 10 Exception-Handling 37 pages listings

runtime exceptions. try/catch. checked exceptions. additional Java statements.

Chapter 11 Abstract Classes and Interfaces 40 pages listings

interfaces. instanceof. polymorphism. Double, Integer, and other wrappers.

Chapter 12 Files and Multidimensional Arrays 36 pages listings

FileReader and FileWriter. StringTokenizer. RandomAccessFile. bytecode.

Chapter 13 Sorting and Searching 34 pages listings

selection sort, insertion sort, big-oh, binary search, quicksort, mergesort. Data Flow Diagrams.

Chapter 14 Stacks and Queues 36 pages listings

implementing stacks, queues, and priority queues with arrays and linked lists.

Chapter 15 Collections and Linked Lists 40 pages listings

implementing Collection, Iterator, and ListIterator with arrays and linked lists.

Appendices are in the same pdf file as the table of contents, a total of 48 pages.

Appendix A Guidelines for Program Style APP-1

Appendix B Glossary of Terms APP-5

Appendix C Common Compile-Time Errors APP-12

Appendix D Java Reserved Words APP-17

Appendix E Sun Standard Library Classes APP-18

Appendix F Major Programming Projects APP-21